Network service providers need to routinely collect flow-level measurements to guide the execution of network management applications. The flow information can be used for customer accounting and traffic engineering, which largely rely on aggregate traffic volume statistics. As the complexity of network management increases, flow monitoring is more and more needed for a number of critical network management tasks, such as anomaly detection, identification of unwanted application traffic, and forensic analysis. This analysis needs to identify and analyze as many distinct flows as possible. One consequence of this increased complexity is a growing demand for fine-grained flow measurements. However, network operators usually do not have prior knowledge of the detailed measurement tasks that the monitoring infrastructure needs to perform. One example of this is security applications. For example, a specific network prefix that is “below the radar” for traffic engineering purposes may play an important role in the early detection of anomalies.
Conventional flow monitoring solutions are inadequate for many of these network management applications. It is a challenging task to develop a flow monitoring technique that is both fine-grained and accurate. Due to computational and storage resource constraints, conventional routers cannot record all packets or flows that pass through them. Thus, there have been a variety of sampling techniques proposed to selectively record as many packets as the routers' CPUs and memory resources allow. For example, many router vendors today implement uniform packet sampling, such as the sampling mechanism provided by NetFlow (see, Cisco Systems NetFlow Services Export Version 9. RFC 3954). In the NetFlow sampling, each router independently selects a packet with a sampling probability (typically between 0.001 and 0.01) and aggregates the selected packets into flow records. This approach is simple so as to be technically feasible. It introduces only a small overhead to the router. However, this approach also reduces the overall quality of other applications that use the flow-level measurement results.
Therefore, existing sampling techniques are not sufficient for the increasing demand of new network management applications. One solution is to continuously increase router computational and storage capabilities. At one extreme, passive monitoring equipment, which captures every packet on a link, allows highly accurate measurements. However, such an approach scales very poorly for large networks, given the high unit cost for deployment and maintenance.